package com.Q08;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @version v1.0.0
 * 创建时间：2022/8/1 09:47
 */
public class Q08_08 {
    ArrayList<String> res;
    LinkedList<Character> track = new LinkedList<>();
    boolean[] used;

    public String[] permutation(String S) {
        res = new ArrayList<>();
        used = new boolean[S.length()];
        char[] chars = S.toCharArray();
        Arrays.sort(chars);
        helper(chars);
        return res.toArray(new String[]{});
    }

    private void helper(char[] chars) {
        if (track.size() == chars.length) {
            Character[] characters = track.toArray(new Character[]{});
            StringBuilder builder = new StringBuilder();
            for (Character character : characters) {
                builder.append(character);
            }
            res.add(builder.toString());
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if (used[i]) {
                continue;
            }
            // 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
            if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
                continue;
            }
            track.add(chars[i]);
            used[i] = true;
            helper(chars);
            track.removeLast();
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        Q08_08 q08_08 = new Q08_08();
        String[] permutation = q08_08.permutation("oss");
        for (String s : permutation) {
            System.out.print(s + " ");
        }
    }
}
